//
//  LinkedListTests.swift
//  AlgorithmsTests
//
//  Created by Archer on 2018/8/8.
//  Copyright © 2018年 Archer. All rights reserved.
//

import XCTest
@testable import SwiftyDSA

class LinkedListTests: XCTestCase {
    
    func testNilValue() {
        let list = LinkedList<String?>()
        list.insertAsLast(nil)
        list.insertAsFirst("hello")
        
        XCTAssertEqual(list[0], "hello")
        XCTAssertEqual(list[1], nil)
        
        list.insertAsFirst(nil)
        XCTAssertNil(list[0])
        
        list[0] = "world"
        XCTAssertNotNil(list[0])
        XCTAssertEqual(list[0], "world")
    }
    
    func testFind() {
        let list = LinkedList<String>()
        list.insertAsFirst("hello")
        list.insertAsLast("world")
        
        XCTAssertNotNil(list[0])
        XCTAssertNotNil(list[1])
        
        XCTAssertNil(list.find("hello", 0, list.last!))
        XCTAssertNotNil(list.find("hello", 1, list.last!))


        list.insertAsFirst("saber")
        list.insertAsFirst("lancer")
        list.insertAsFirst("archer")
        list.insertAsLast("assassin")
        list.insertAsLast("rider") // archer lancer saber hello world assassin rider

        XCTAssertEqual(list.find("lancer", 1, list.last!), nil)
        XCTAssertEqual(list.find("lancer", 3, list.last!), nil)
        XCTAssertEqual(list.find("lancer", 5, list.last!), list.first?.successor)
        
        XCTAssertEqual(list.find("lancer", 7, list.last!), list.first?.successor)
        XCTAssertEqual(list.find("lancer", 100, list.last!), list.first?.successor)
        
        XCTAssertEqual(list.find("archer", 4, list.last!.predecessor!), nil)
        XCTAssertEqual(list.find("archer", 5, list.last!.predecessor!), list.first)
        XCTAssertEqual(list.find("archer", 5, list.last!.predecessor!), list.first?.successor?.predecessor)
        
        list.insertAsFirst("archer")
        XCTAssertFalse(list.find("archer", 6, list.last!.predecessor!) === list.first)
        XCTAssertTrue(list.find("archer", 6, list.last!.predecessor!) === list.first?.successor)
        XCTAssertEqual(list.find("archer", 5, list.last!.predecessor!), list.first?.successor)
        
        
        list.remove(list.first!)
        XCTAssertEqual(list.find("saber", list.first!, 1), nil)
        
        XCTAssertTrue(list.first?.successor?.successor?.value == "saber")
        XCTAssertEqual(list.find("saber", list.first!, 2), list.first?.successor?.successor)

        list.insertAsLast("saber")
        XCTAssertTrue(list.find("saber", list.first!, 3) === list.first?.successor?.successor)
        XCTAssertEqual(list.last, list.findLast("saber"))
        XCTAssertTrue(list.find("saber", list.first!, 3) !== list.last)
    }
    
    func testExpressibleByArrayLiteral() {
        let list: LinkedList = ["hello", "world", "this", "is",  "Tom", "speaking"]
        print("initial = ", list)
        
        let other = LinkedList(list)
        print("other = ", other)
        
        XCTAssertTrue(list.count == 6)
        XCTAssertTrue(list.count == other.count)
        XCTAssertEqual(list.first?.value, list[0])
        XCTAssertEqual(other.last?.value, other[other.count - 1])
    }
    
    func testDeduplicate() {
        for _ in 0..<3 {
            var totalCount = 0
            let v = LinkedList<Int>()
            for _ in 0..<15 {
                var times = Int(arc4random_uniform(10) + 1) // 5
                let e = times
                if v.findFirst(e) == nil {
                    totalCount += (times - 1)
                    while times > 0  {
                        v.insertAsLast(e)
                        times -= 1
                    }
                }
            }
            print("list = \(v)")
            XCTAssertEqual(v.deduplicate(), totalCount)
            print("list = \(v)")
        }

        // 随机出现
        let v: LinkedList = [0, 1, 1, 9, 8, 7, 9, 8, 7, 6, 5, 4, 4, 5, 6, 6, 6, 0]
        XCTAssertEqual(v.deduplicate(), 10)
        
    }

    func testUniquify() {
        for _ in 0..<3 {
            var totalCount = 0
            let v = LinkedList<Int>()
            for i in 0..<100 {
                var times = Int(arc4random_uniform(10))
                if times > 0 {
                    totalCount += (times - 1)
                }
                while times > 0 {
                    v.insertAsLast(i)
                    times -= 1
                }
            }
            print("list = \(v)")
            let count = v.count
            XCTAssertEqual(v.uniquify(), totalCount)
            XCTAssertEqual(v.count, count - totalCount)
            print("list = \(v)")
        }
    }
    
    func testReverse() {
        let list = LinkedList<String>()
        list.insertAsFirst("h")
        list.insertAsFirst("e")
        list.insertAsFirst("l")
        list.insertAsFirst("l")
        list.insertAsFirst("o") // o l l e h
        
        print("before = ", list)
        list.reverse()
        print("after = ", list)

//        var s = ""
//        list.forEach { s += $0 }
//        XCTAssertEqual(s, "hello")
    }
    
    
    func testDisordered() {
        let list = LinkedList<Int>()
        for i in 0..<100 {
            list.insertAsFirst(i)
        }
        XCTAssertEqual(list.disordered(), 99)
    }
    
    func testSort() {
        
        let list: LinkedList = [1, 2]
        list.sort()
        XCTAssertEqual(list.disordered(), 0)
        
        for _ in 0..<5 {
            let v = LinkedList<Int>()
            for _ in 0..<1000 {
                v.insertAsLast(Int(arc4random_uniform(10000)))
            }
            
            DSABenchmark({
                v.sort()
            }) { (costs) in
                print("耗时 = \(costs)")
            }
            
            XCTAssertEqual(v.disordered(), 0)
        }
    }
    
    func testRemove() {
        let list = LinkedList<String>()
        list.insertAsFirst("hello")
        list.insertAsLast("world")
        
        list.forEach { print($0 + " ") }
    }
    
}
